from typing import List


class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        # 处理result比words更短的情况：因为没有前导0，所以一定无法实现
        length = len(result)
        for word in words:
            if len(word) > length:
                return False

        # ---------- 整理字符情况 ----------
        # 统计所有的变量
        params = set(result)
        for word in words:
            params |= set(word)

        # 枚举所有数字的可能选择
        maybe = {ch: {i for i in range(10)} for ch in params}

        # 所有的数没有前导零 -> 所有开头的数字都不是0
        for word in words:
            if len(word) > 1:
                maybe[word[0]] -= {0}
        if len(result) > 1:
            maybe[result[0]] -= {0}

        # 统计左侧每一位的字符情况
        left_param = [[] for _ in range(length)]
        for word in words:
            for i in range(1, len(word) + 1):
                left_param[-i].append(word[-i])

        # 统计右侧每一位的字符情况
        right_param = [[] for _ in range(length)]
        for i in range(1, len(result) + 1):
            right_param[-i].append(result[-i])

        # [剪枝1]最高位只在右侧出现：右侧最高位的值小于等于左侧最高位数量-1（若左侧最高数数量为1，则等于1）
        if len(left_param[0]) == 0:
            maybe[result[0]] -= {i for i in range(max(2, len(left_param[1])), 10)}

            # [剪枝2]最高位只在右侧出现，左侧次高位只有1个值：左侧次高位的值为9，右侧次高位的值为0
            if len(left_param[1]) == 1:
                maybe[left_param[1][0]] = {9}
                maybe[result[1]] = {0}

        # print(left_param)
        # print(right_param)
        # for ch, choose in maybe.items():
        #     print(ch, ":", choose)

        candidate = {i for i in range(10)}

        # 填写已经确定的字母
        nums = {}
        for ch, choose in maybe.items():
            if len(choose) == 1:
                nums[ch] = choose.pop()
                candidate.remove(nums[ch])

        # print("候选数字:", candidate)

        # 深度优先搜索
        def dfs(pos, i, inc1=0):
            # print("DFS:", pos, i)

            # 跳过已赋值的左侧元素
            while i < len(left_param[pos]) and left_param[pos][i] in nums:
                i += 1

            # 已经搜索到尽头的情况
            if pos == 0 and i == len(left_param[0]):
                right_ch = result[pos]
                right_val = sum(nums[ch] for ch in left_param[pos]) + inc1
                if right_ch in nums:
                    return nums[result[pos]] == right_val
                else:
                    return right_val in maybe[right_ch] & candidate

            # 左侧已经赋值完毕
            if i == len(left_param[pos]):
                right_ch = result[pos]
                right_val = sum(nums[ch] for ch in left_param[pos]) + inc1
                inc2 = right_val // 10
                right_val %= 10
                if right_ch in nums:
                    if nums[right_ch] == right_val:
                        return dfs(pos - 1, 0, inc2)
                    else:
                        return False
                else:
                    if right_val in candidate and right_val in maybe[right_ch]:
                        nums[right_ch] = right_val
                        candidate.remove(right_val)
                        if dfs(pos - 1, 0, inc2):
                            return True
                        nums.pop(right_ch)
                        candidate.add(right_val)
                        return False
                    else:
                        return False

            # 左侧尚未赋值完毕
            else:
                left_ch = left_param[pos][i]
                for v in maybe[left_ch] & candidate:
                    nums[left_ch] = v
                    candidate.remove(v)
                    if dfs(pos, i + 1, inc1):
                        return True
                    nums.pop(left_ch)
                    candidate.add(v)
                return False

        return dfs(length - 1, 0)


if __name__ == "__main__":
    print(Solution().isSolvable(words=["SEND", "MORE"], result="MONEY"))  # True
    print(Solution().isSolvable(words=["SIX", "SEVEN", "SEVEN"], result="TWENTY"))  # True
    print(Solution().isSolvable(words=["THIS", "IS", "TOO"], result="FUNNY"))  # True
    print(Solution().isSolvable(words=["LEET", "CODE"], result="POINT"))  # False

    # 测试用例7/32
    print(Solution().isSolvable(words=["BUT", "ITS", "STILL"], result="FUNNY"))  # True

    # 测试用例15/32
    print(Solution().isSolvable(words=["JACAH", "IIJI", "GACG"], result="DDJF"))  # False
